#include <stdio.h>
#include <malloc.h>

#define MaxSize 50
typedef int ElemType;
/**
 * 顺序表结构
 */
typedef struct {
    ElemType data[MaxSize];        //存放顺序表元素
    int length;                    //存放顺序表的长度
} SqList;

/**
 * 建立顺序表
 * @param L
 * @param a
 * @param n
 */
void CreateList(SqList *&L, ElemType a[], int n) {
    L = (SqList *) malloc(sizeof(SqList));
    for (int i = 0; i < n; i++)
        L->data[i] = a[i];
    L->length = n;
}

/**
 * 初始化顺序表
 * @param L
 */
void InitList(SqList *&L) {
    L = (SqList *) malloc(sizeof(SqList));    //分配存放线性表的空间
    L->length = 0;
}

/**
 * 销毁顺序表
 * @param L
 */
void DestroyList(SqList *&L) {
    free(L);
}

/**
 * 判断顺序表是否为空
 * @param L
 * @return
 */
bool ListEmpty(SqList *L) {
    return (L->length == 0);
}

/**
 * 返回顺序表长度
 * @param L
 * @return
 */
int ListLength(SqList *L) {
    return (L->length);
}

/**
 * 显示顺序表所有元素
 * @param L
 */
void DispList(SqList *L) {
    for (int i = 0; i < L->length; i++)
        printf("%d ", L->data[i]);
    printf("\n");
}

/**
 * 获取顺序表第i个元素
 * @param L
 * @param i
 * @param e
 * @return
 */
bool GetElem(SqList *L, int i, ElemType &e) {
    if (i < 1 || i > L->length)
        return false;
    e = L->data[i - 1];
    return true;
}

/**
 * 顺序表中定位元素e首次出现的位置
 * @param L
 * @param e
 * @return
 */
int LocateElem(SqList *L, ElemType e) {
    int i = 0;
    while (i < L->length && L->data[i] != e) i++;
    if (i >= L->length)
        return 0;
    else
        return i + 1;
}

/**
 * 在顺序表中第i个位置上插入元素e
 * @param L
 * @param i
 * @param e
 * @return
 */
bool ListInsert(SqList *&L, int i, ElemType e) {
    int j;
    if (i < 1 || i > L->length + 1)
        return false;
    i--;                        //将顺序表位序转化为elem下标
    for (j = L->length; j > i; j--)    //将data[i]及后面元素后移一个位置
        L->data[j] = L->data[j - 1];
    L->data[i] = e;
    L->length++;                //顺序表长度增1
    return true;
}

/**
 * 删除顺序表中第i个位置上的元素，用参数e返回
 * @param L
 * @param i
 * @param e
 * @return
 */
bool ListDelete(SqList *&L, int i, ElemType &e) {
    int j;
    if (i < 1 || i > L->length)
        return false;
    i--;                        //将顺序表位序转化为elem下标
    e = L->data[i];
    for (j = i; j < L->length - 1; j++)    //将data[i]之后的元素前移一个位置
        L->data[j] = L->data[j + 1];
    L->length--;                //顺序表长度减1
    return true;
}

/**
 * Demo2.3
 * 删除顺序表L中所有值为x的元素
 * 解决方案：重建方法,找见一个不等于x的元素即向前移动，覆盖K位置元素交换
 * @param L :顺序表
 * @param x :待删除元素
 */
void DelNode1(SqList *&L, ElemType x) {
    //k记录不等于待删元素X的 元素数量
    int k = 0, i;
    for (int i = 0; i < L->length; ++i) {
        if (L->data[i] != x) {
            L->data[k] = L->data[i];
            k++;
        }
    }
    L->length = k;
}

/**
 * Demo2.3
 * 删除顺序表L中所有值为x的元素
 * 解决案：前移法,
 * @param L :顺序表
 * @param x :待删除元素
 */
void DelNode2(SqList *&L, ElemType x) {
    //k记录等于代删元素X的 元素数量
    int k = 0, i = 0;
    while (i < L->length) {
        if(L->data[i]==x){
            k++;
        }else{
            L->data[i-k] = L->data[i];
        }
        i++;
    }
}
